TNotes.leetcode

Appearance

0463. 岛屿的周长【简单】

0463. 岛屿的周长【简单】 ​

1. 📝 题目描述 ​

给定一个 row x col 的二维网格地图 grid，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100。计算这个岛屿的周长。

示例 1：

img

txt
输入：grid = [
  [0, 1, 0, 0],
  [1, 1, 1, 0],
  [0, 1, 0, 0],
  [1, 1, 0, 0]
]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

示例 2：

txt
输入：grid = [[1]]
输出：4

示例 3：

txt
输入：grid = [[1,0]]
输出：4

提示：

  • row == grid.length
  • col == grid[i].length
  • 1 <= row, col <= 100
  • grid[i][j] 为 0 或 1

2. 🎯 s.1 - 暴力统计法 ​

js
/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function (grid) {
  if (!grid || grid.length === 0 || grid[0].length === 0) {
    return 0
  }

  const rows = grid.length
  const cols = grid[0].length
  let perimeter = 0

  // 遍历每个格子
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      // 如果当前格子是陆地，依次检查四个方向，判断每条边是否需要计入周长。
      if (grid[i][j] === 1) {
        // 上方向
        if (i === 0 || grid[i - 1][j] === 0) {
          perimeter++
        }
        // 下方向
        if (i === rows - 1 || grid[i + 1][j] === 0) {
          perimeter++
        }
        // 左方向
        if (j === 0 || grid[i][j - 1] === 0) {
          perimeter++
        }
        // 右方向
        if (j === cols - 1 || grid[i][j + 1] === 0) {
          perimeter++
        }
      }
    }
  }

  return perimeter
}
  • 时间复杂度：O(m×n)，其中 m 和 n 分别是网格的行数和列数，需要遍历整个网格
  • 空间复杂度：O(1)，只使用了常数级别的额外空间
  • 算法思路：
    • 遍历每个格子，如果为陆地，则检查其四个方向（上、下、左、右）
    • 如果某个方向是边界或者水域，则贡献一个边长到周长

3. 🎯 s.2 - 数学计数法 ​

js
/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function (grid) {
  let landCount = 0 // 陆地格子总数
  let adjacentCount = 0 // 相邻的陆地边数

  // 遍历网格统计陆地格子数和相邻边数
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === 1) {
        landCount++

        // 检查下方是否有陆地
        if (i + 1 < grid.length && grid[i + 1][j] === 1) {
          adjacentCount++
        }

        // 检查右方是否有陆地
        if (j + 1 < grid[0].length && grid[i][j + 1] === 1) {
          adjacentCount++
        }
      }
    }
  }

  // 每个陆地格子贡献4条边，每条相邻边被两个格子共享，所以要减去2倍的相邻边数
  return landCount * 4 - adjacentCount * 2
}
  • 时间复杂度：O(m×n)，其中 m 和 n 分别是网格的行数和列数，需要遍历整个网格
  • 空间复杂度：O(1)，只使用了常数级别的额外空间
  • 算法思路：
    • 统计陆地格子总数
    • 统计相邻的陆地边数
      • 对于每个陆地格子，只检查其右边和下边的格子是否也是陆地（这样可以避免重复计算）
      • 如果右边是陆地，则 adjacentCount 加 1
      • 如果下边是陆地，则 adjacentCount 加 1
    • 周长 = 陆地格子数 × 4 - 相邻边数 × 2

Discussions